/* Memory management module for Project GHome 
 * Author: SUN Haoyu 
 * Janurary, 2012
 */

#include <stdio.h>
#include <unistd.h>

#include "gmalloc.h"

#define AVAILABLE 1
#define UNAVAILABLE 0



struct mem_control_block {
   int is_available;
   int size;
   struct mem_control_block * next_block;
   struct mem_control_block * previous_block;
};

int has_initialized = 0; //mem initialisation indicator
void *managed_memory_start;
void *last_valid_address;

//show allocation table

void show_mem_blocks(){
	struct mem_control_block *mcb;
	int counter = 0;

	
	mcb = managed_memory_start;
	
	printf("memory blocks : \n");
	while(mcb != NULL){
		printf("block %d  size %d @ %d  %s\n",counter,mcb->size,(int)mcb, mcb->is_available? "free":"allocated");
		counter ++;
		mcb = mcb->next_block;
	}
	printf("end of list\n");

}


//todo: implement pre-allocate shit
void malloc_init()
{
	/* get last valid address*/
	last_valid_address = sbrk(0);
	
	managed_memory_start = last_valid_address;
	
	/* allocate first block(s) of the chain */
	
	int numbytes;
	struct mem_control_block * first_mcb;
	numbytes = sizeof(struct mem_control_block) + sizeof(int);
	numbytes = 7 * numbytes;
	last_valid_address = sbrk(numbytes) + numbytes;
	first_mcb = managed_memory_start;
	
	first_mcb -> is_available = AVAILABLE;
	first_mcb -> size = numbytes;
	first_mcb -> previous_block = NULL;
	first_mcb -> next_block = NULL;
	
	/*finish allocating first block */
	printf("Memory initialized\n");
	show_mem_blocks();
	printf("first address : %d\n", (int) managed_memory_start);
	
	printf("last address : %d\n", (int)  last_valid_address);
	
	has_initialized = 1;
	
	
}





void gfree(void *firstbyte) {
	// the current mcb
	struct mem_control_block *mcb;
	// the mcb that will be fused with this
	struct mem_control_block *fusion_mcb;
	//temporary mcbs
	struct mem_control_block *fusion_mcb_next;
	struct mem_control_block *fusion_mcb_prev;
	

	mcb = firstbyte - sizeof(struct mem_control_block);

	
	
	//trying to fuse with the previous block
	fusion_mcb = mcb-> previous_block;
	if(fusion_mcb != NULL){
		if ( fusion_mcb-> is_available){
			printf("fuse with the previous block\n");
			
			//fusion the sizes
			fusion_mcb->size = fusion_mcb->size + mcb->size;
			
			
			//delete current block from the double chained list
			fusion_mcb_next = mcb->next_block;
		
			fusion_mcb->next_block = mcb->next_block;
	
			if(fusion_mcb_next != NULL){
				fusion_mcb_next->previous_block = fusion_mcb;
			}
			printf("block @%d & @%d are fused.\n",(int)mcb, (int)fusion_mcb);
			
			mcb = fusion_mcb;
		}
	}
	
	
	//trying to fuse with the next block
	fusion_mcb = mcb-> next_block;
	if(fusion_mcb != NULL){
		if ( fusion_mcb-> is_available){
			printf("fuse with the next block\n");
				
			//fusion the sizes
			mcb->size = fusion_mcb->size + mcb->size;
			//delete current block from the double chained list
			mcb->next_block = fusion_mcb->next_block;
			fusion_mcb_next = fusion_mcb->next_block;
			if(fusion_mcb_next != NULL){
				fusion_mcb_next->previous_block = mcb;
			}
			printf("block @%d & @%d are fused.\n",(int)mcb, (int)fusion_mcb);
			
		}			
	}


	mcb->is_available = AVAILABLE;
	
	
	
	return;
}




void *gmalloc(long numbytes) {
   /* search pointer*/
   void *current_location;
   struct mem_control_block *current_location_mcb;
   
   /* This is the memory location we will return.  It will
   * be set to 0 until we find something suitable
   */
   void *memory_location;
   
   /* memorize the previous block in case of allocating 
    * a new block
    */
      
   void *prev_location; 
   struct mem_control_block *prev_location_mcb;
   /* check if its first time run and initialise if first time */
   if(! has_initialized) {
       malloc_init();
   }
   
   /*this size info is for creating new block */
   numbytes = numbytes + sizeof(struct mem_control_block);
   
   /* Set memory_location to 0 until we find a suitable location*/
   memory_location = 0;
   /* Begin searching at the start of managed memory */
   current_location = managed_memory_start;
   
   /* Keep going until we have searched all allocated space 
   or find a suitable free block*/
  
   while(current_location != NULL)
   {
   /* current_location and current_location_mcb point to the same address. */
       current_location_mcb = (struct mem_control_block *)current_location;
       if(current_location_mcb->is_available)
       {
			//omg its a free block		
           if(current_location_mcb->size >= numbytes)
           {
           
               /* It is no longer available */
              
               current_location_mcb->is_available = UNAVAILABLE;
               
               
               
               memory_location = current_location;
               
               // trying to split the block into 2 pieces 
      	       if((current_location_mcb->size - numbytes) >=    
               (sizeof(struct mem_control_block)+sizeof(int))){
               		struct mem_control_block * new_mcb;
               		struct mem_control_block * new_mcb_next;
               		
               		// new block address and its size
               		new_mcb = current_location_mcb + numbytes;
               		new_mcb->size = current_location_mcb->size - numbytes;
               		
               		//also change size for the former block
               		current_location_mcb->size = numbytes;
               		
               		/* insert the new block between the 2 neighbours */
               	
               		new_mcb->previous_block = current_location_mcb;
               		new_mcb->next_block = current_location_mcb->next_block;
               		new_mcb_next = current_location_mcb->next_block;
               		current_location_mcb->next_block = new_mcb;
               		
               		new_mcb->is_available = AVAILABLE;
               		
               		//printf("after split: %d & %d\n",(int) current_location_mcb,(int) current_location_mcb->next_block);
               		
               
               		
               		if(new_mcb_next !=NULL){
               			new_mcb_next->previous_block = new_mcb;
               		}
               }
              
              
               break;//exit loop when finding a free block
           }
       }
	   prev_location = current_location;   //need optimize
       current_location = current_location_mcb->next_block;
       
       
       /*
       if(current_location != NULL){
        printf("im @ %d\n", (int)current_location);
 		} else
 		{
 		printf("im @ null address\n");
 		}
 		*/
   }
   
   /*ask for more memory if cant find a free block*/
   if(! memory_location)
   {
   
   		
   
       /* Move the program break numbytes further */
       sbrk(numbytes);
       /* The new memory will be where the last valid
        address left off*/
       memory_location = last_valid_address;
       /* move the last valid address forward numbytes*/
       last_valid_address = last_valid_address + numbytes;
       /*initialize the mem_control_block */
       current_location_mcb = memory_location;
       current_location_mcb->is_available = UNAVAILABLE;
       current_location_mcb->size = numbytes;
       current_location_mcb->previous_block = prev_location;
       prev_location_mcb = prev_location;
       prev_location_mcb->next_block = current_location_mcb;
       current_location_mcb->next_block = NULL;
       
       
       
       
       
       printf("new last address : %d\n",(int)last_valid_address);
   }
  
   /* Move the pointer past the mem_control_block */
   memory_location = memory_location + sizeof(struct mem_control_block);
   
   return memory_location;
}




int main( int argc, const char* argv[] )
{

	int * pt;
	int * ptt;
	int * pttt;
	
	
	
	printf( "\ntrying gmalloc int 5\n" );
	
	pt = (int *) gmalloc(sizeof(int));
	
	
	*pt = 5;
	printf("%d\n",*pt);
	//printf("current location: %d",(int)pt);
	show_mem_blocks();
	gfree(pt);
	show_mem_blocks();
	printf( "\ntrying gmalloc int 6\n" );


	pt = (int *) gmalloc(sizeof(int));
	*pt = 6;
	printf("%d\n",*pt);
	//printf("current location: %d",(int)pt);
	gfree(pt);

	show_mem_blocks();
	

	printf( "\ntrying gmalloc int 1 & 2 & 3\n" );
	
	pt = (int *) gmalloc(sizeof(int));
	ptt = (int *) gmalloc(sizeof(int));
	pttt = (int *) gmalloc(sizeof(int));
	
	*pt = 1;
	*ptt = 2;
	*pttt = 3;
	
	show_mem_blocks();
	
	printf("%d & %d & %d\n",*pt,*ptt,*pttt);
	//printf("current location: %d\n",(int)pt);
	//printf("current location: %d\n",(int)ptt);
	//printf("current location: %d\n",(int)pttt);
	gfree(pt);
	gfree(ptt);
	gfree(pttt);
	
	
	show_mem_blocks();
	
	
}


